We present measurements of the triaxial dark matter halo shapes and alignment correlation functions in the Millennium and Millennium-2 dark matter N-body simulations. These two simulations allow us to measure the distributions of halo shapes down to 10% of the virial radius over a halo mass range of 6E9 - 2E14 M_sun/h. We largely confirm previous results on the distributions of halo axis ratios as a function of halo mass, but we find that the median angle between halo major axes at different halo radii can vary by a factor of 2 between the Millennium-1 and 2 simulations because of the different mass resolution. Thus, error in the shape determinations from limited resolution is potentially degenerate with the misalignment of halo inner and outer shapes used to constrain Brightest Cluster Galaxy alignments in previous works. We also present simplifying parameterizations for the 3-D halo-mass alignment correlation functions that are necessary ingredients for triaxial halo models of large-scale structure and models of galaxy intrinsic alignments as contaminants for cosmic shear surveys. We measure strong alignments between halos of all masses and the surrounding dark matter overdensities out to several tens of Mpc/h, in agreement with observed shear-galaxy and cluster shape correlations. We use these measurements to forecast the contribution to the weak lensing signal around galaxy clusters from correlated mass along the line-of-sight. For prolate clusters with major axes aligned with the line-of-sight the fraction of the weak lensing signal from mass external to the cluster can be twice that predicted if the excess halo alignment correlation is assumed to be zero.